﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace Jenvin.Library.DataStruct
{
    public class BloomFilter
    {
        private BitArray hashbits;
        private int numKeys;
        private int[] hashKeys;

        private Func<string, int>[] hashFuncs = null;
        /// <summary>
        /// 布隆过滤.因为的两个HashFucntion(k=2).
        /// 如果保证冲突率最小. K=(m/n)ln2=0.7(m/n);其中 m 这多少个数据容器.n为多少个key。
        /// 你可以通过ReplaceHash.替换本生所有的Hash函数 。
        /// http://en.wikipedia.org/wiki/Bloom_filter
        /// </summary>
        /// <param name="tableSize"></param>
        /// <param name="nKeys">多少个Hash Key</param>
        public BloomFilter(int tableSize, int nKeys)
        {
            numKeys = nKeys;
            hashKeys = new int[numKeys];
            hashbits = new BitArray(tableSize);

            hashFuncs = new Func<string, int>[2];

            hashFuncs[0] = x => x.GetHashCode();
            hashFuncs[1] = x => HashString(x);
        }

        //public void RegisterHash(Func<string,int> hashFn)
        //{
        //    if (hashFn == null) throw new ArgumentNullException("");
        //    Func<string, int>[]  newFuncs = new Func<string, int>[hashFuncs.Length + 1];
        //    Array.Copy(hashFuncs, 0, newFuncs, 0, hashFuncs.Length);
        //    newFuncs[hashFuncs.Length] = hashFn;

        //    hashFuncs = newFuncs;
        //}

        public void ReplaceHash(Func<string, int> hashFn, Func<string, int> hashFn2)
        {
            //if (hashFns == null && hashFns.Length == 0)
            //    throw new ArgumentException("");

            if (hashFn == null)
                throw new ArgumentNullException();
            if (hashFn2 == null)
                throw new ArgumentNullException();

            hashFuncs[0] = x => x.GetHashCode();
            hashFuncs[1] = x => HashString(x);

        }

        private void CreateHashes(string str)
        {
            int hash1 = hashFuncs[0](str);
            int hash2 = hashFuncs[1](str);

            hashKeys[0] =(hash1& 0x7fffffff) % hashbits.Count;
            if (numKeys > 1)
            {
                for (int i = 1; i < numKeys; i++)
                {
                    hashKeys[i] =((hash1 + (i * hash2))&0x7fffffff)
                        % hashbits.Count;
                }
            }
        }

        public bool Contain(string str)
        {
            CreateHashes(str);
            // Test each hash key.  Return false if any 
            //  one of the bits is not set.
            foreach (int hash in hashKeys)
            {
                if (!hashbits[hash])
                    return false;
            }
            // All bits set.  The item is there.
            return true;
        }

        public bool Add(string str)
        {
            // Initially assume that the item is in the table
            bool rslt = true;
            CreateHashes(str);
            foreach (int hash in hashKeys)
            {
                if (!hashbits[hash])
                {
                    // One of the bits wasn't set, so show that
                    // the item wasn't in the table, and set that bit.
                    rslt = false;
                    hashbits[hash] = true;
                }
            }
            return rslt;
        }


        private int HashString(string s)
        {
            int hash = 0;

            for (int i = 0; i < s.Length; i++)
            {
                hash += s[i];
                hash += (hash << 10);
                hash ^= (hash >> 6);
            }
            hash += (hash << 3);
            hash ^= (hash >> 11);
            hash += (hash << 15);
            return hash;
        }
    }

}
